import java.util.*;

/**
 * @author LI DUO
 * @version 1.0
 * @date 2019/9/29 上午 09:57
 */
public class day190929 {
    /**
     dp[i][j]表示从[i,j]中猜出正确数字所需要的最少花费金额.(dp[i][i] = 0)
     假设在范围[i,j]中选择x, 则选择x的最少花费金额为: max(dp[i][x-1], dp[x+1][j]) + x
     用max的原因是我们要计算最坏反馈情况下的最少花费金额(选了x之后, 正确数字落在花费更高的那侧)

     初始化为(n+2)*(n+2)数组的原因: 处理边界情况更加容易, 例如对于求解dp[1][n]时x如果等于1, 需要考虑dp[0][1](0不可能出现, dp[0][n]为0)
     而当x等于n时, 需要考虑dp[n+1][n+1](n+1也不可能出现, dp[n+1][n+1]为0)

     如何写出相应的代码更新dp矩阵, 递推式dp[i][j] = min(max(dp[i][x-1], dp[x+1][j]) + x), x~[i:j], 可以画出矩阵图协助理解, 可以发现
     dp[i][x-1]始终在dp[i][j]的左部, dp[x+1][j]始终在dp[i][j]的下部, 所以更新dp矩阵时i的次序应当遵循bottom到top的规则, j则相反, 由于
     i肯定小于等于j, 所以我们只需要遍历更新矩阵的一半即可(下半矩阵)
     **/
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 2][n + 2];
        for (int i = n; i >= 1; --i) {
            for (int j = i; j <= n; ++j) {
                if (i == j) {
                    dp[i][j] = 0;
                } else {
                    dp[i][j] = Integer.MAX_VALUE;
                    for (int x = i; x <= j; ++x) {
                        dp[i][j] = Math.min(dp[i][j], Math.max(dp[i][x - 1], dp[x + 1][j]) + x);
                    }
                }
            }
        }
        return dp[1][n];
    }

    public boolean uniqueOccurrences(int[] arr) {
        int[] map = new int[2000];
        for (int i : arr) {
            map[i + 1000]++;
        }
        HashSet<Integer> hashSet = new HashSet<>();
        for (int i : map) {
            if (i == 0) {
                continue;
            }
            if (hashSet.contains(i)) {
                return false;
            }
            hashSet.add(i);
        }
        return true;
    }

    public int equalSubstring(String s, String t, int maxCost) {
        int ret = 0, nowCost = 0, n = s.length();
        for (int l = 0, r = 0; r < n; ++r) {
            nowCost += Math.abs(s.charAt(r) - t.charAt(r));
            while (nowCost > maxCost) {
                nowCost -= Math.abs(s.charAt(l) - t.charAt(l));
                ++l;
            }
            ret = Math.max(ret, r - l + 1);
        }
        return ret;
    }

    public static void main(String[] args) {
        day190929 day190929 = new day190929();
//        System.out.println(day190929.equalSubstring("pxezla", "loewbi", 25));
        System.out.println(day190929.equalSubstring("krrgw", "zjxss", 19));
//        System.out.println(day190929.removeDuplicates("deeedbbcccbdaa", 3));
    }

    public String removeDuplicates(String s, int k) {
        StringBuilder builder = new StringBuilder(s);
        boolean del = true;
        while (del) {
            del = false;
            char cur = builder.charAt(0);
            int curIndex = 0;
            int curLen = 1;
            for (int i = 1; i < builder.length(); i++) {
                char charAt = builder.charAt(i);
                if (charAt == cur) {
                    curLen++;
                    if (curLen == k) {
                        builder.delete(curIndex, i + 1);
                        curLen = 0;
                        del = true;
                    }
                } else {
                    cur = charAt;
                    curLen = 1;
                    curIndex = i;
                }
            }
        }
        return builder.toString();
    }

    public int minimumMoves(int[][] grid) {
        int n = grid.length;
        if (grid[n - 1][n - 2] == 1 || grid[n - 1][n - 1] == 1) {
            return -1;
        }
        List<Integer> start = Arrays.asList(0, 0, 0, 1);
        List<Integer> target = Arrays.asList(n - 1, n - 2, n - 1, n - 1);
        Set<List<Integer>> visited = new HashSet<>();
        Queue<List<Integer>> queue = new LinkedList<>();
        queue.offer(start);
        visited.add(start);
        int moves = 0;
        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            for (int i = 0; i < queueSize; i++) {
                List<Integer> curr = queue.poll();
                if (curr.equals(target)) {
                    return moves;
                }
                int r1 = curr.get(0);
                int c1 = curr.get(1);
                int r2 = curr.get(2);
                int c2 = curr.get(3);
                List<List<Integer>> nextMoves = new ArrayList<>(4);
                nextMoves.add(moveRight(n, grid, r1, c1, r2, c2));
                nextMoves.add(moveDown(n, grid, r1, c1, r2, c2));
                nextMoves.add(rotateClockwise(n, grid, r1, c1, r2, c2));
                nextMoves.add(rotateCounterClockwise(n, grid, r1, c1, r2, c2));
                for (List<Integer> next : nextMoves) {
                    if (next != null && !visited.contains(next)) {
                        visited.add(next);
                        queue.offer(next);
                    }
                }
            }
            moves++;
        }
        return -1;
    }

    private List<Integer> moveRight(int n, int[][] grid, int r1, int c1, int r2, int c2) {
        if (r1 + 1 == r2 && c1 == c2 && c1 + 1 < n && grid[r1][c1 + 1] == 0 && grid[r2][c2 + 1] == 0) {
            return Arrays.asList(r1, c1 + 1, r2, c2 + 1);
        }
        if (c1 + 1 == c2 && r1 == r2 && c2 + 1 < n && grid[r2][c2 + 1] == 0) {
            return Arrays.asList(r1, c1 + 1, r2, c2 + 1);
        }
        return null;
    }

    private List<Integer> moveDown(int n, int[][] grid, int r1, int c1, int r2, int c2) {
        if (r1 + 1 == r2 && c1 == c2 && r2 + 1 < n && grid[r2 + 1][c2] == 0) {
            return Arrays.asList(r2, c1, r2 + 1, c2);
        }
        if (c1 + 1 == c2 && r1 == r2 && r1 + 1 < n && grid[r1 + 1][c1] == 0 && grid[r2 + 1][c2] == 0) {
            return Arrays.asList(r1 + 1, c1, r2 + 1, c2);
        }
        return null;
    }

    private List<Integer> rotateClockwise(int n, int[][] grid, int r1, int c1, int r2, int c2) {
        if (c1 + 1 == c2 && r1 == r2 && r1 + 1 < n && grid[r1 + 1][c1] == 0 && grid[r2 + 1][c2] == 0) {
            return Arrays.asList(r1, c1, r1 + 1, c1);
        }
        return null;
    }

    private List<Integer> rotateCounterClockwise(int n, int[][] grid, int r1, int c1, int r2, int c2) {
        if (r1 + 1 == r2 && c1 == c2 && c1 + 1 < n && grid[r1][c1 + 1] == 0 && grid[r2][c2 + 1] == 0) {
            return Arrays.asList(r1, c1, r1, c2 + 1);
        }
        return null;
    }
}
